package io.adrainty.algorithm.leetcode.normal;

import java.util.Arrays;

/**
 * @author adrainty
 * @version v1.0.0
 * @since 2024/12/23 上午11:13
 */
public class Solution16 {

    public static int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int minGap = Integer.MAX_VALUE;
        int res = 0;

        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == target) return sum;
                if (Math.abs(sum - target) < minGap) {
                    minGap = Math.abs(sum - target);
                    res = sum;
                }
                if (sum > target) right--;
                else left++;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(threeSumClosest(new int[]{-1, 2, 1, -4}, 1));
    }
}
